import random

def genetic_algorithm_knapsack(W, weights, values, N, pop_size=100, generations=100, mutation_rate=0.01):
    # 初始化种群（随机生成 pop_size 个个体，每个是个体 0/1 串）
    def create_individual():
        return [random.randint(0, 1) for _ in range(N)]
    
    population = [create_individual() for _ in range(pop_size)]
    
    def fitness(individual):
        total_weight = sum(w * i for w, i in zip(weights, individual))
        total_value = sum(v * i for v, i in zip(values, individual))
        return total_value if total_weight <= W else 0  # 超重则适应度为 0
    
    def select_parents(population):
        # 轮盘赌选择（按适应度比例选择）
        fitnesses = [fitness(ind) for ind in population]
        total_fitness = sum(fitnesses)
        if total_fitness == 0:
            return random.choices(population, k=2)  # 避免除零
        probs = [f / total_fitness for f in fitnesses]
        return random.choices(population, weights=probs, k=2)
    
    def crossover(parent1, parent2):
        # 单点交叉
        point = random.randint(1, N - 1)
        child1 = parent1[:point] + parent2[point:]
        child2 = parent2[:point] + parent1[point:]
        return child1, child2
    
    def mutate(individual):
        # 按 mutation_rate 随机变异
        for i in range(N):
            if random.random() < mutation_rate:
                individual[i] = 1 - individual[i]  # 0↔1 翻转
        return individual
    
    best_individual = None
    best_fitness = 0
    
    for _ in range(generations):
        new_population = []
        
        # 精英保留（直接保留最优个体）
        current_best = max(population, key=fitness)
        if fitness(current_best) > best_fitness:
            best_fitness = fitness(current_best)
            best_individual = current_best.copy()
        
        # 生成新一代
        while len(new_population) < pop_size:
            parent1, parent2 = select_parents(population)
            child1, child2 = crossover(parent1, parent2)
            child1 = mutate(child1)
            child2 = mutate(child2)
            new_population.extend([child1, child2])
        
        population = new_population[:pop_size]  # 保持种群大小
    
    # 返回最优解
    final_best = max(population, key=fitness)
    total_weight = sum(w * i for w, i in zip(weights, final_best))
    total_value = sum(v * i for v, i in zip(values, final_best))
    return total_value, final_best, total_weight

# 示例
W = 10
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
N = len(weights)
max_val, solution, total_w = genetic_algorithm_knapsack(W, weights, values, N)
print("最大价值（遗传算法）:", max_val)  # 接近 10
print("选择的物品（1=选，0=不选）:", solution)
print("总重量:", total_w)